翻訳と辞書 Words near each other ・ String Quartet No. 3 (Bartók) ・ String Quartet No. 3 (Beethoven) ・ String Quartet No. 3 (Brahms) ・ String Quartet No. 3 (Carter) ・ String Quartet No. 3 (Dvořák) ・ String Quartet No. 3 (Mendelssohn) ・ String Quartet No. 3 (Nielsen) ・ String Quartet No. 3 (Piston) ・ String Quartet No. 3 (Rochberg) ・ String Quartet No. 3 (Rouse) ・ String Quartet No. 3 (Schubert) ・ String Quartet No. 3 (Shostakovich) ・ String Quartet No. 3 (Spohr) ・ String girdling Earth ・ String grammar ・ String graph ・ String group ・ String instrument ・ String instrument repertoire ・ String interning ・ String interpolation ・ String kernel ・ String Lake ・ String Lake Comfort Station ・ String Lake Trail ・ String Lakes ・ String literal ・ String metric ・ String noise ・ String octet Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク String graph ： ウィキペディア英語版 String graph In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph ''G'', ''G'' is a string graph if and only if there exists a set of curves, or strings, drawn in the plane such that no three strings intersect at a single point and such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to ''G''. == Background == described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now classical family of interval graphs. Later, specified the same idea to electrical networks and printed circuits. The mathematical study of string graphs began with the paper and through a collaboration between Sinden and Ronald Graham, where the characterization of string graphs eventually came to be posed as an open question at the 5th Hungarian Colloquium on Combinatorics in 1976.〔.〕 However, the recognition of string graphs was eventually proven to be NP-complete, implying that no simple characterization is likely to exist.〔 showed string graph recognition to be NP-hard, but was not able to show that it could be solved in NP. After intermediate results by and , completed the proof that the problem is NP-complete.〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「String graph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.